package com.njupt.graphTheory;



import java.util.*;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/4 15:49
 * @Description: 210. 课程表 II 拓扑排序
 * @Version: 1.0
 */


public class FindOrder_210_dfs {

    //用来标记拓扑排序中是否有环
    public boolean isValid = true;

    /**
     * 法一：使用深度优先遍历实现拓扑排序
     * 深度遍历时，当遍历到当前节点u时如果u的所有相邻节点全都遍历完成，此时一定时递归回溯到节点u的情况，u的相邻节点都已经在栈中了，此时栈顶到栈底的元素正好是拓扑排序的情况
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {

        //1、构造邻接表，已经状态数组
        List<List<Integer>> graph = new ArrayList<>();
        int[] isVisited = new int[numCourses];
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<Integer>());
        }
        //构造邻接表
        for (int[] prerequisite : prerequisites) {
            graph.get(prerequisite[1]).add(prerequisite[0]);
        }

        for (int i = 0; i < numCourses; i++) {
            if(isVisited[i] == 0){
                //2、深度优先遍历的拓扑排序
                dfs(graph,i,isVisited,stack);
            }
        }

        // TODO 返回值
        if(!isValid){
            return new int[0];
        }
        return stack.stream().mapToInt(Integer::intValue).toArray();
    }

    private void dfs(List<List<Integer>> graph, int u,int[] isVisited,Deque<Integer> stack) {
        //1、对当前遍历的节点u标记为正在遍历中
        isVisited[u] = 1;
        //2、遍历节点u的所有邻接节点，对于正在遍历的节点v
        for (Integer v : graph.get(u)) {
            if(isVisited[v.intValue()] == 0){
                //2.1、如果节点v没有遍历过那么进行深度优先遍历
                dfs(graph,v.intValue(),isVisited,stack);
                if(!isValid){
                    return;
                }
            }else if(isVisited[v.intValue()] == 1){
                //2.2、如果节点v是正在遍历，表示有环，程序直接返回
                isValid = false;
                return;
            }
        }
        //3、当节点u的所有邻接点遍历完成说明是回溯到了节点u，此时u可以入栈。
        isVisited[u] = 2; //表示已经遍历完成
        stack.push(u);
    }

    public static void main(String[] args) {
        FindOrder_210_dfs test = new FindOrder_210_dfs();
//        int[][] prerequisites = {{1,0},{2,0},{3,1},{3,2}};
        int[][] prerequisites = {{0,1},{1,0}};
        int[] order = test.findOrder(4, prerequisites);
        System.out.println(Arrays.toString(order));
    }

}
